A graph is called \emph{claw-free} if it contains no induced subgraphisomorphic to $K_{1,3}$. Matthews and Sumner proved that a 2-connectedclaw-free graph $G$ is hamiltonian if every vertex of it has degree at least$(|V(G)|-2)/3$. At the workshop C\&C (Novy Smokovec, 1993), Broersmaconjectured the degree condition of this result can be restricted only toend-vertices of induced copies of $N$ (the graph obtained from a triangle byadding three disjoint pendant edges). Fujisawa and Yamashita showed that thedegree condition of Matthews and Sumner can be restricted only to end-verticesof induced copies of $Z_1$ (the graph obtained from a triangle by adding onependant edge). Our main result in this paper is a characterization of allgraphs $H$ such that a 2-connected claw-free graph $G$ is hamiltonian if eachend-vertex of every induced copy of $H$ in $G$ has degree at least$|V(G)|/3+1$. This gives an affirmative solution of the conjecture of Broersmaup to an additive constant.
展开▼
机译：如果图不包含与$ K_ {1,3} $相同的诱导亚同形，则它称为\ emph {claw-free}。 Matthews和Sumner证明，如果每个顶点的度数至少为$（| V（G）| -2）/ 3 $，则2个无爪的连通图$ G $是哈密顿量。在车间C \＆C（Novy Smokovec，1993）中，Broersma猜想该结果的程度条件只能限于$ N $的诱导副本的顶点（通过添加三个不相交的垂线边缘从三角形获得的图形）。 Fujisawa和Yamashita指出Matthews和Sumner的度数条件只能限于$ Z_1 $的诱导副本的最终顶点（通过添加一个垂线边从三角形获得的图形）。我们在本文中的主要结果是对所有图$ H $进行刻画，使得如果$ G $中每个$ H $的诱导副本的每个顶点的顶点度至少为$，则2连通无爪图$ G $是哈密顿量。 | V（G）| / 3 + 1 $。这给出了Broersmaup猜想对加性常数的肯定解。
展开▼
